package com.zklh.leetcode.top100;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 直方图中的最大面积算法实现
 *
 * @version 1.0
 * @Author tongnan
 * @Date 2023/11/10
 */
public class SolutionLCR039 {
    public int largestRectangleArea(int[] heights) {
        Deque<Integer> deque = new LinkedList<>();
        int[] left = new int[heights.length];
        int[] right = new int[heights.length];
        for (int i = 0; i < heights.length; i++) {
            while (!deque.isEmpty() && heights[deque.peek()] >= heights[i]) {
                right[deque.peek()] = i;
                deque.poll();
            }
            left[i] = deque.isEmpty() ? -1 : deque.peek();
            deque.push(i);
        }
        while (!deque.isEmpty()) {
            right[deque.poll()] = heights.length;
        }

        int maxArea = 0;

        for (int i = 0; i < heights.length; i++) {
            maxArea = Math.max(maxArea, heights[i] * (right[i] - left[i] - 1));
        }
        return maxArea;
    }

    public static void main(String[] args) {
        SolutionLCR039 solutionLCR039 = new SolutionLCR039();
        System.out.println(solutionLCR039.largestRectangleArea(new int[]{2,1,5,6,2,3}));
    }
}